SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Coffman–Graham algorithm</title>

</head>

Coffman–Graham algorithm

</h1>

</header>

The Coffman–Graham algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> for arranging the elements of a <a href="Partially_ordered_set" title="Partially ordered set">partially ordered set</a> into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

It is named after <a href="Edward_G._Coffman%2C_Jr." class="mw-redirect" title="Edward G. Coffman, Jr.">Edward G. Coffman, Jr.</a> and <a href="Ronald_Graham" title="Ronald Graham">Ronald Graham</a>, who published it in 1972 for an application in <a href="Job_shop_scheduling" class="mw-redirect" title="Job shop scheduling">job shop scheduling</a>. In this application, the elements to be ordered are jobs, the bound W is the number of jobs that can be scheduled at any one time, and the partial order describes prerequisite relations between the jobs. The goal is to find a schedule that completes all jobs in minimum total time. Subsequently, the same algorithm has also been used in <a href="Graph_drawing" title="Graph drawing">graph drawing</a>, as a way of placing the vertices of a <a href="Directed_graph" title="Directed graph">directed graph</a> into layers of fixed widths so that most or all edges are directed consistently downwards.

For a partial ordering given by its <a href="Transitive_reduction" title="Transitive reduction">transitive reduction</a> (covering relation), the Coffman–Graham algorithm can be implemented in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a> using the <a href="Partition_refinement" title="Partition refinement">partition refinement</a> data structure as a subroutine. If the transitive reduction is not given, it takes <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> to construct it.

<div class="mw-heading mw-heading2"><h2 id="Problem_statement_and_applications">Problem statement and applications</h2></div>

In the version of the job shop scheduling problem solved by the Coffman–Graham algorithm, one is given a set of n jobs J1, J2, ..., Jn, together with a system of precedence constraints Ji < Jj requiring that job Ji be completed before job Jj begins. Each job is assumed to take unit time to complete. The scheduling task is to assign each of these jobs to time slots on a system of W identical processors, minimizing the <a href="Makespan" title="Makespan">makespan</a> of the assignment (the time from the beginning of the first job until the completion of the final job). Abstractly, the precedence constraints define a partial order on the jobs, so the problem can be rephrased as one of assigning the elements of this partial order to levels (time slots) in such a way that each time slot has at most as many jobs as processors (at most W elements per level), respecting the precedence constraints. This application was the original motivation for Coffman and Graham to develop their algorithm.<a href="#cite_note-cg72-1">[1]</a><a href="#cite_note-2">[2]</a>

In the <a href="Layered_graph_drawing" title="Layered graph drawing">layered graph drawing</a> framework outlined by <a href="#CITEREFSugiyamaTagawaToda1981">Sugiyama, Tagawa & Toda (1981)</a><a href="#cite_note-3">[3]</a> the input is a <a href="Directed_graph" title="Directed graph">directed graph</a>, and a drawing of a graph is constructed in several stages:<a href="#cite_note-bett-4">[4]</a><a href="#cite_note-5">[5]</a>

<ol><li>A <a href="Feedback_arc_set" title="Feedback arc set">feedback arc set</a> is chosen, and the edges of this set reversed, in order to convert the input into a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> with (if possible) few reversed edges.</li>

<li>The vertices of the graph are given integer y-coordinates in such a way that, for each edge, the starting vertex of the edge has a higher coordinate than the ending vertex, with at most W vertices sharing the same y-coordinate. In this way, all edges of the directed acyclic graph and most edges of the original graph will be oriented consistently downwards.</li>

<li>Dummy vertices are introduced within each edge so that the subdivided edges all connect pairs of vertices that are in adjacent levels of the drawing.</li>

<li>Within each group of vertices with the same y-coordinate, the vertices are <a href="Permutation" title="Permutation">permuted</a> in order to minimize the <a href="Crossing_number_(graph_theory)" title="Crossing number (graph theory)">number of crossings</a> in the resulting drawing, and the vertices are assigned x-coordinates consistently with this permutation.</li>

<li>The vertices and edges of the graph are drawn with the coordinates assigned to them.</li></ol>

In this framework, the y-coordinate assignment again involves grouping elements of a partially ordered set (the vertices of the graph, with the <a href="Reachability" title="Reachability">reachability</a> ordering on the vertex set) into layers (sets of vertices with the same y-coordinate), which is the problem solved by the Coffman–Graham algorithm.<a href="#cite_note-bett-4">[4]</a> Although there exist alternative approaches than the Coffman–Graham algorithm to the layering step, these alternatives in general are either not able to incorporate a bound on the maximum width of a level or rely on complex <a href="Integer_programming" title="Integer programming">integer programming</a> procedures.<a href="#cite_note-6">[6]</a>

More abstractly, both of these problems can be formalized as a problem in which the input consists of a partially ordered set and an integer W. The desired output is an assignment of integer level numbers to the elements of the partially ordered set such that, if x < y is an ordered pair of related elements of the partial order, the number assigned to x is smaller than the number assigned to y, such that at most W elements are assigned the same number as each other, and minimizing the difference between the smallest and the largest assigned numbers.

<div class="mw-heading mw-heading2"><h2 id="The_algorithm">The algorithm</h2></div>

The Coffman–Graham algorithm performs the following steps.<a href="#cite_note-bett-4">[4]</a>

<ol><li>Represent the partial order by its <a href="Transitive_reduction" title="Transitive reduction">transitive reduction</a> or <a href="Covering_relation" title="Covering relation">covering relation</a>, a directed acyclic graph G that has an edge from x to y whenever x < y and there does not exist any third element z of the partial order for which x < z < y. In the graph drawing applications of the Coffman–Graham algorithm, the resulting directed acyclic graph may not be the same as the graph being drawn, and in the scheduling applications it may not have an edge for every precedence constraint of the input: in both cases, the transitive reduction removes redundant edges that are not necessary for defining the partial order.</li>

<li>Construct a <a href="Topological_sorting" title="Topological sorting">topological ordering</a> of G in which the vertices are ordered <a href="Lexicographic_order" title="Lexicographic order">lexicographically</a> by the set of positions of their incoming neighbors. To do so, add the vertices one at a time to the ordering, at each step choosing a vertex v to add such that the incoming neighbors of v are all already part of the partial ordering, and such that the most recently added incoming neighbor of v is earlier than the most recently added incoming neighbor of any other vertex that could be added in place of v. If two vertices have the same most recently added incoming neighbor, the algorithm breaks the tie in favor of the one whose second most recently added incoming neighbor is earlier, etc.</li>

<li>Assign the vertices of G to levels in the reverse of the topological ordering constructed in the previous step. For each vertex v, add v to a level that is at least one step higher than the highest level of any outgoing neighbor of v, that does not already have W elements assigned to it, and that is as low as possible subject to these two constraints.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Analysis">Analysis</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Output_quality">Output quality</h3></div>

As <a href="#CITEREFCoffmanGraham1972">Coffman & Graham (1972)</a> originally proved, their algorithm computes an optimal assignment for W = 2; that is, for scheduling problems with unit length jobs on two processors, or for layered graph drawing problems with at most two vertices per layer.<a href="#cite_note-cg72-1">[1]</a> A closely related algorithm also finds the optimal solution for scheduling of jobs with varying lengths, allowing pre-emption of scheduled jobs, on two processors.<a href="#cite_note-7">[7]</a> For W > 2, the Coffman–Graham algorithm uses a number of levels (or computes a schedule with a makespan) that is within a factor of 2 − 2/W of optimal.<a href="#cite_note-ls77-8">[8]</a><a href="#cite_note-bt94-9">[9]</a> For instance, for W = 3, this means that it uses at most 4/3 times as many levels as is optimal. When the partial order of precedence constraints is an <a href="Interval_order" title="Interval order">interval order</a>, or belongs to several related classes of partial orders, the Coffman–Graham algorithm finds a solution with the minimum number of levels regardless of its width bound.<a href="#cite_note-10">[10]</a>

As well as finding schedules with small makespan, the Coffman–Graham algorithm (modified from the presentation here so that it topologically orders the <a href="Reverse_graph" class="mw-redirect" title="Reverse graph">reverse graph</a> of G and places the vertices as early as possible rather than as late as possible) minimizes the total flow time of two-processor schedules, the sum of the completion times of the individual jobs. A related algorithm can be used to minimize the total flow time for a version of the problem in which preemption of jobs is allowed.<a href="#cite_note-11">[11]</a>

<div class="mw-heading mw-heading3"><h3 id="Time_complexity">Time complexity</h3></div>

<a href="#CITEREFCoffmanGraham1972">Coffman & Graham (1972)</a> and <a href="#CITEREFLenstraRinnooy_Kan1978">Lenstra & Rinnooy Kan (1978)</a><a href="#cite_note-12">[12]</a> state the time complexity of the Coffman–Graham algorithm, on an n-element partial order, to be O(n2). However, this analysis omits the time for constructing the transitive reduction, which is not known to be possible within this bound. <a href="#CITEREFSethi1976">Sethi (1976)</a> shows how to implement the topological ordering stage of the algorithm in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a>, based on the idea of <a href="Partition_refinement" title="Partition refinement">partition refinement</a>.<a href="#cite_note-13">[13]</a> Sethi also shows how to implement the level assignment stage of the algorithm efficiently by using a <a href="Disjoint-set_data_structure" title="Disjoint-set data structure">disjoint-set data structure</a>. In particular, with a version of this structure published later by <a href="#CITEREFGabowTarjan1985">Gabow & Tarjan (1985)</a>, this stage also takes linear time.<a href="#cite_note-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 35em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCoffmanGraham1972" class="citation cs2"><a href="Edward_G._Coffman%2C_Jr." class="mw-redirect" title="Edward G. Coffman, Jr.">Coffman, E. G. Jr.</a>; <a href="Ronald_Graham" title="Ronald Graham">Graham, R. L.</a> (1972), <a rel="nofollow" class="external text" href="http://www.math.ucsd.edu/~ronspubs/72_04_two_processors.pdf">"Optimal scheduling for two-processor systems"</a> (PDF), <a href="Acta_Informatica" title="Acta Informatica">Acta Informatica</a>, 1 (3): 200–213, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbf00288685">10.1007/bf00288685</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0334913">0334913</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:40603807">40603807</a></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFLeung2004" class="citation cs2">Leung, Joseph Y.-T. (2004), "Some basic scheduling algorithms", Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-58488-397-5</bdi></cite>.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFSugiyamaTagawaToda1981" class="citation cs2 cs1-prop-long-vol">Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Methods for visual understanding of hierarchical system structures", <a href="IEEE_Systems%2C_Man%2C_and_Cybernetics_Society" title="IEEE Systems, Man, and Cybernetics Society">IEEE Transactions on Systems, Man, and Cybernetics</a>, SMC-11 (2): 109–125, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTSMC.1981.4308636">10.1109/TSMC.1981.4308636</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0611436">0611436</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8367756">8367756</a></cite>.

</li>

<li id="cite_note-bett-4">^ <a href="#cite_ref-bett_4-0">a</a> <a href="#cite_ref-bett_4-1">b</a> <a href="#cite_ref-bett_4-2">c</a> <cite id="CITEREFdi_BattistaEadesTamassiaTollis1999" class="citation cs2">di Battista, Giuseppe; <a href="Peter_Eades" title="Peter Eades">Eades, Peter</a>; <a href="Roberto_Tamassia" title="Roberto Tamassia">Tamassia, Roberto</a>; Tollis, Ioannis G. (1999), "Chapter 9: Layered drawings of digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302</cite>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBastertMatuszewski2001" class="citation cs2">Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; <a href="Dorothea_Wagner" title="Dorothea Wagner">Wagner, Dorothea</a> (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-44969-8_5">10.1007/3-540-44969-8_5</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-42062-0</bdi></cite>. Bastert and Matuszewski also include a description of the Coffman–Graham algorithm; however, they omit the transitive reduction stage of the algorithm.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFHealyNikolov2002" class="citation cs2">Healy, Patrick; Nikolov, Nikola S. (2002), "How to layer a directed acyclic graph", <a href="International_Symposium_on_Graph_Drawing" title="International Symposium on Graph Drawing">Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers</a>, Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, pp. 16–30, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45848-4_2">10.1007/3-540-45848-4_2</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-43309-5</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1962416">1962416</a></cite>.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFMuntzCoffman1969" class="citation cs2">Muntz, R. R.; <a href="Edward_G._Coffman%2C_Jr." class="mw-redirect" title="Edward G. Coffman, Jr.">Coffman, E. G.</a> (1969), "Optimal preemptive scheduling on two-processor systems", <a href="IEEE_Transactions_on_Computers" title="IEEE Transactions on Computers">IEEE Transactions on Computers</a>, 18 (11): 1014–1020, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FT-C.1969.222573">10.1109/T-C.1969.222573</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:206617438">206617438</a></cite>.

</li>

<li id="cite_note-ls77-8"><a href="#cite_ref-ls77_8-0">^</a> <cite id="CITEREFLamSethi1977" class="citation cs2">Lam, Shui; <a href="Ravi_Sethi" title="Ravi Sethi">Sethi, Ravi</a> (1977), "Worst case analysis of two scheduling algorithms", <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 6 (3): 518–536, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0206037">10.1137/0206037</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0496614">0496614</a></cite>.

</li>

<li id="cite_note-bt94-9"><a href="#cite_ref-bt94_9-0">^</a> <cite id="CITEREFBraschiTrystram1994" class="citation cs2">Braschi, Bertrand; Trystram, Denis (1994), "A new insight into the Coffman–Graham algorithm", <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 23 (3): 662–669, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539790181889">10.1137/S0097539790181889</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1274650">1274650</a></cite>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFChardonMoukrim2005" class="citation cs2">Chardon, Marc; Moukrim, Aziz (2005), "The Coffman-Graham algorithm optimally solves UET task systems with overinterval orders", <a href="SIAM_Journal_on_Discrete_Mathematics" title="SIAM Journal on Discrete Mathematics">SIAM Journal on Discrete Mathematics</a>, 19 (1): 109–121, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0895480101394999">10.1137/S0895480101394999</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2178187">2178187</a></cite>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFCoffmanSethuramanTimkovsky2003" class="citation cs2"><a href="Edward_G._Coffman%2C_Jr." class="mw-redirect" title="Edward G. Coffman, Jr.">Coffman, E. G. Jr.</a>; Sethuraman, J.; Timkovsky, V. G. (2003), "Ideal preemptive schedules on two processors", <a href="Acta_Informatica" title="Acta Informatica">Acta Informatica</a>, 39 (8): 597–612, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00236-003-0119-6">10.1007/s00236-003-0119-6</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1996238">1996238</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7016804">7016804</a></cite>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFLenstraRinnooy_Kan1978" class="citation cs2"><a href="Jan_Karel_Lenstra" title="Jan Karel Lenstra">Lenstra, J. K.</a>; <a href="Alexander_Rinnooy_Kan" title="Alexander Rinnooy Kan">Rinnooy Kan, A. H. G.</a> (1978), "Complexity of scheduling under precedence constraints", Operations Research, 26 (1): 22–35, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fopre.26.1.22">10.1287/opre.26.1.22</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10338.dmlcz%2F141477">10338.dmlcz/141477</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/169889">169889</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0462553">0462553</a></cite>.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFSethi1976" class="citation cs2"><a href="Ravi_Sethi" title="Ravi Sethi">Sethi, Ravi</a> (1976), "Scheduling graphs on two processors", SIAM Journal on Computing, 5 (1): 73–82, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0205005">10.1137/0205005</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0398156">0398156</a></cite>.

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFGabowTarjan1985" class="citation cs2"><a href="Harold_N._Gabow" title="Harold N. Gabow">Gabow, Harold N.</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert Endre</a> (1985), "A linear-time algorithm for a special case of disjoint set union", Journal of Computer and System Sciences, 30 (2): 209–221, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2885%2990014-5">10.1016/0022-0000(85)90014-5</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0801823">0801823</a></cite>.

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-16" href="https://en.wikipedia.org/wiki/?title=Coffman%E2%80%93Graham_algorithm&oldid=1276027910">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>